package leetcode.weekly.week304;

import java.util.HashMap;
import java.util.Map;

//Solution4Test
public class Solution4 {

	public int longestCycle(int[] edges) {
		int n = edges.length;
		int ans = -1;
		Integer[] ids = new Integer[n];
		int[] cnts = new int[n];
		int id = 0;
		int[] map = new int[n];
		for (int i = 0; i < n; i++) {
			if (ids[i] == null) {
				int cur = i;
				int cnt = 0;
				while (cur != -1 && ids[cur] == null) {
					ids[cur] = id;
					cnts[cur] = cnt++;
					cur = edges[cur];
				}
				if (cur != -1 && ids[cur] != null) {
					if (ids[cur] == id) {
						int curAns = cnt - cnts[cur];
						ans = Math.max(ans, curAns);
						map[id] = curAns;
					} else {
						map[id] = map[ids[cur]];
					}
				}
				id++;
			}
		}
		return ans;
	}

}
